package com.xiaoyg.algorithm.sort;


public class MergeSort {
    public static void main(String[] args) {
        int [] nums = {2,4,3,5,6,2};
        mergeSort(nums);

        System.out.println(nums);
    }

    public static void mergeSort(int [] nums) {
        sort(nums, 0, nums.length - 1);
    }

    private static void sort(int[] nums, int lo, int hi) {
        if(lo == hi){
            return;
        }

        int mid = lo + (hi - lo) / 2;

        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);

        merge(nums, lo, mid, hi);
    }

    private static void merge(int[] nums, int lo, int mid, int hi) {
        int [] temp = new int [nums.length];
        for (int i = lo; i <= hi; i++) {
            temp[i] = nums[i];
        }

        int i = lo;
        int j = mid + 1;

        for (int p = lo;p <=hi ;p++){
            if (i == mid + 1){
                //左侧已经合并
                nums[p] = temp[j];
                j++;
            }else if (j == hi + 1){
                //右侧已经合并
                nums[p] = temp[i];
                i++;
            } else if(temp[i] > temp[j]){
                nums[p] = temp[j];
                j++;
            }else {
                nums[p] = temp[i];
                i++;
            }
        }

    }


}
